Lexing & Parsing

3+(5-4)
위의 산술 표현식을 계산하기 위해 구문 분석(parse)를 수행한다.
렉싱(Lexing)
렉싱은 표현식을 해석하는 첫 단계이다.
문자열 입력을 토큰(token) 단위로 나누어 나열한다.
(토큰은 문법상에서 의미를 가지는 최소 단위를 의미)
struct Token{
enum Type{ integer, plus, minus, lparen, rparen} type;
strint text;
explicit Token(Type type, const string& text): type(type), text(text) {}
friend ostream& operator<<(ostream& os, const Token& obj){
return os<<"'"<<obj.text<<"'";
}
};
vector<Token> lex(const string& input){
vector<Token> result;
for(int i=0; i<input.size(); ++i){
switch(input[i]){
case '+':
result.push_back(Token{Token::plus, "+"});
break;
case '-':
result.push_back(Token{Token::minus, "-"});
break;
case '(':
result.push_back(Token{Token::lparen, "("});
break;
case ')':
result.push_back(Token{Token::rparen, ")"});
break;
default:
ostringstream buffer;
buffer<<input[i];
for(int j=i+1; j<input.size(); ++j){
if(isdigit(input[j])){
buffer<<input[j];
++i;
} else {
result.push_back(Token{Token::integer, buffer.str()});
break;
}
}
}
}
}
덧셈, 뺄셈 기호처럼 확정적인 토큰은 파싱하기 간단하지만,
숫자에 대해서는 연이어 오는 수와 같은 별도의 처리 루틴을 요한다.
파싱(Parsing)
파싱은 토큰의 나열을 의미있는 단위로 바꾼다.
의미있는 단위로 묶기 위해서 데이터 구조 위에 모든 타입을 감싸는 최상단 추상 부모 타입을 이용한다.
struct Element{
virtual int eval() const=0;
};
struct Integer: Element{
int value;
explicit Integer(const int value): value(value) {}
int eval() const override {
return value;
}
};
struct BinaryOperation: Element{
enum Type{ addition, subtraction } type;
shared_ptr<Element> lhs, rhs;
int eval() const override {
if(type==addition) return lhs->eval()+rhs->eval();
return lhs->eval()-rhs->eval();
}
};
// 파싱(토큰 나열 표현식에 대한 이진 트리 변환)
shared_ptr<Element> parse(const vector<Token>& tokens){
auto result=make_unique<BinaryOperation>();
bool have_lhs=false;
for(size_t i=0; i<tokens.size(); i++){
auto token=tokens[i];
switch(tokne.type){
case Token::integer:
int value=boost::lexical_cast<int>(token.text);
auto integer=make_shared<Integer>(value);
if(!have_lhs){
result->lhs=integer;
have_lhs=true;
} else result->rhs=integer;
}
case Token::plus:
result->type=BinaryOperation::addition;
break;
case Token::minus;
result->type=BinaryOperation::subtraction;
break;
case Token::lparen:
int j=i;
for(; j<token.size(); ++j){
if(tokens[j].type==Token::rparen) break;
}
vector<Token> subexpression(&tokens[i+1], &tokens[j]);
auto element=parse(subexpression); // 재귀 호출
if(!have_lhs){
result->lhs=element;
have_lhs=true;
} else {
result->rhs=elemnt;
i=j;
}
}
return result;
}
연산자의 경우, 왼쪽과 오른쪽에 모두 항목들을 가진다.
하지만, 숫자의 경우 표현식의 왼쪽에 위치할지, 오른쪽에 위치하게 될지 알 수 없다.
따라서 have_lhs 변수를 이용해서 이를 기록한다.
// 사용
string input{ "(13-4)-(12+1)" };
auto tokens=lex(input);
auto parsed=parse(tokens);
cout<<input<<" = "<<parsed->eval()<<endl;